package d28

// 123. 买卖股票的最佳时机 III
// 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
//
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
//
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

func maxProfit2(prices []int) int {

	// 初始维度为5，分别表示 0-未交易, 1-交易一次持有股票 2-交易一次不持有
	// 3-交易两次持有，4-交易两次不持有
	dp := make([][]int, len(prices))
	for idx, _ := range prices {
		dp[idx] = make([]int, 5)
	}
	dp[0] = []int{0, -prices[0], 0, -prices[0], 0}

	for i := 1; i < len(prices); i++ {
		dp[i][0] = dp[i-1][0]
		dp[i][1] = IntMax2(dp[i-1][1], dp[i-1][0]-prices[i])
		dp[i][2] = IntMax2(dp[i-1][1]+prices[i], dp[i-1][2])
		dp[i][3] = IntMax2(dp[i-1][2]-prices[i], dp[i-1][3])
		dp[i][4] = IntMax2(dp[i-1][3]+prices[i], dp[i-1][4])
	}
	return dp[len(prices)-1][4]
}

func IntMax2(a, b int) int {
	if a > b {
		return a
	}
	return b
}
